package com.kfm.base.structure;

import java.util.Arrays;

public class MyStack extends Stack{

    /*
        存元素的数组
     */
    private Object[] value;

    /*
       元素的个数
       下一个元素的下标
     */
    private int length;


    /**
     * 默认容量
     */
    private static final int DEFAULT_CAPACITY = 10;

    public MyStack(){
        this(DEFAULT_CAPACITY);
    }

    public MyStack(int capacity){
        if (capacity < 0){
            capacity = DEFAULT_CAPACITY;
        }
        value = new Object[capacity];
    }


    @Override
    public void push(Object element) {
        // length < value.length
        if (length + 1 > value.length){
            grow(); // 扩容
        }
        // value[length ++] = element;
        value[length] = element;
        length ++;
    }

    /**
     * 扩容
     */
    private void grow() {
        int oldCapacity = value.length;
        // old + old >> 1
        int newCapacity = oldCapacity << 1;

        // 确认新的容量比旧的大
        if (newCapacity < oldCapacity){
            newCapacity = Integer.MAX_VALUE;
        }

        value = Arrays.copyOf(value, newCapacity);
    }

    @Override
    public Object pop() {
        // 栈顶元素
//        Object element = value[-- length];
        Object element = value[length - 1]; // 被删除的元素
        value[length - 1] = null; // 置空
        length --; // 少一个元素
        return element;
    }

    @Override
    public Object peek() {
        return value[length - 1];
    }

    @Override
    public boolean isEmpty() {
        return length == 0;
    }

    @Override
    public int size() {
        return length;
    }

    @Override
    public String toString(){
        StringBuilder sb = new StringBuilder();
        sb.append("[");
        for (int i = 0; i < length - 1; i++) {
            sb.append(value[i] + ", ");
        }
        sb.append(value[length - 1]).append("]");

        return sb.toString();
    }
}
